//
//  TreeSolution.swift
//  Swift-Learning-Demo
//
//  Created by yuan xiaodong on 2021/1/6.
//  Copyright © 2021 yuan. All rights reserved.
//  二叉树

import Foundation

class TreeSolution {
    init() {
        
    }
    
    // MARK: - *********** 【94】二叉树的中序遍历 难度:中等 ***********
    /**
     示例 1：
     输入：root = [1,null,2,3]
     输出：[1,3,2]
     
     示例 2：
     输入：root = []
     输出：[]
     
     示例 3：
     输入：root = [1]
     输出：[1]
     
     方法一：递归

     思路与算法

     首先我们需要了解什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。
     */
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [Int]() }

        var ret = [Int]()
        var worklist = [TreeNode]()
        var n : TreeNode? = root

        while !worklist.isEmpty || n != nil {
            if n != nil {
                worklist.append(n!)
                n = n!.left
            } else {
                n = worklist.popLast()
                ret.append(n!.val)
                n = n!.right
            }
        }
        return ret
    }
    
    // MARK: - *********** 【95】不同的二叉搜索树 II 难度:中等 ***********
    /**
     给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
     
     示例 1：
     输入：n = 3
     输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
     
     示例 2：
     输入：n = 1
     输出：[[1]]
     
     解题思路

     穷举root节点的所有可能。
     递归构造出左右子树的所有合法 BST。
     给root节点穷举所有左右子树的组合。
     */
    func generateTrees(_ n: Int) -> [TreeNode?] {
        if n == 0 {
            return [TreeNode?]()
        }
        // 构造闭区间 [1, n] 组成的 BST
        return build(1,n)
    }
    
    /* 构造闭区间 [lo, hi] 组成的 BST */
    func build(_ start : Int,_ end : Int) -> [TreeNode?] {
        var res = [TreeNode?]()
        
        // base case，显然当start > end闭区间[start, end]肯定是个空区间，也就对应着空节点 null，
        if (start > end){
            res.append(nil)
            return res
        }
        if (start == end){
            let node = TreeNode(start)
            res.append(node)
            return res
        }
        
        // 1、穷举 root 节点的所有可能。
        for i in start...end{
            // 2、递归构造出左右子树的所有合法 BST。
            let left = build(start, i-1)
            let right = build(i+1, end)
            // 3、给 root 节点穷举所有左右子树的组合。
            for leftNode in left {
                for rightNode in right {
                    let node = TreeNode(i)
                    node.left = leftNode
                    node.right = rightNode
                    res.append(node)
                }
            }
        }
        return res
    }
    
    // MARK: - *********** 【96】不同的二叉搜索树 难度:中等 ***********
    /**
     给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？
     返回满足题意的二叉搜索树的种数。
     示例1：
     输入：n = 3
     输出：5
     
     示例2：
     输入：n = 1
     输出：1
     
     提示：
     1 <= n <= 19
     */
    //方法一：动态规划
    func numTrees(_ n: Int) -> Int {
        if n <= 1 {
            return 1
        }
        var dp = [Int](repeating: 0, count: n + 1)
        dp[0] = 1
        dp[1] = 1
        for i in 2...n {
            for j in 1...i {
                dp[i] += dp[j - 1] * dp[i - j]
            }
        }
        return dp[n]
    }
    
    //方法二：数学，卡塔兰数
    func numTrees2(_ n: Int) -> Int {
        var C = 1
        for i in 0..<n {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return C
    }
    
    // MARK: - *********** 【98】验证二叉搜索树 难度:中等 ***********
    /**
     给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

     有效 二叉搜索树定义如下：

     节点的左子树只包含 小于 当前节点的数。
     节点的右子树只包含 大于 当前节点的数。
     所有左子树和右子树自身必须也是二叉搜索树。

     示例1
     输入：root = [2,1,3]
     输出：true
     
     示例2
     输入：root = [5,1,4,null,null,3,6]
     输出：false
     解释：根节点的值是 5 ，但是右子节点的值是 4 。
     */
    func isValidBST(_ root: TreeNode?) -> Bool {
        return isValidBSTRecursive(root, Int.min, Int.max)
    }
    
    func isValidBSTRecursive(_ node: TreeNode?, _ min: Int,_ max: Int) -> Bool {
        if let currentNode = node {
            if currentNode.val < max && currentNode.val > min && isValidBSTRecursive(currentNode.left, min, currentNode.val) && isValidBSTRecursive(currentNode.right, currentNode.val, max){
                return true
            }
        } else {
            return true
        }
        return false
    }
    
    //Tree上下界法
    func isValidBST_2(_ root: TreeNode?) -> Bool {
        return isValidBST_S(root, Int.min, Int.max)
    }
    
    func isValidBST_S(_ node: TreeNode?, _ left: Int,_ right: Int) -> Bool {
        var is_ok = true
        if node == nil {
            return true
        }
        
        //值不在上下界之内放回false
        if let current = node {
            if !((left < current.val) && (current.val < right)){
                return false
            }
        }
        //检查当前节点在上下界中
        
        //检查左子树在上下界中
        if let current = node {
            if current.left != nil {
                is_ok = isValidBST_S(current.left, left, current.val);
            }
            if is_ok == false {
                return false
            }
        }
        
        //检查右子树在上下界中
        if let current = node {
            if current.right != nil {
                is_ok = isValidBST_S(current.right, current.val,right);
            }
            if is_ok == false {
                return false
            }
        }
        
        //到这都符合
        return true
    }
    
    // MARK: - *********** 【99】恢复二叉搜索树 难度:中等 ***********
    /**
     给你二叉搜索树的根节点 root ，该树中的两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树。
     示例1
     输入：root = [1,3,null,null,2]
     输出：[3,1,null,null,2]
     解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
     
     示例2
     输入：root = [3,1,4,null,null,2]
     输出：[2,1,4,null,null,3]
     解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
     */
    var biggerNode: TreeNode? = nil
    var samllerNode: TreeNode? = nil
    var node = TreeNode(-Int.max)
    
    func inorderTraverse(_ root: TreeNode) {
        if root.left != nil {
            inorderTraverse(root.left!)
        }
        
        if biggerNode == nil && root.val <= node.val {
            biggerNode = node
        }
        
        if root.val < node.val {
            samllerNode = root
        }
        
        node = root
        
        if root.right != nil {
            inorderTraverse(root.right!)
        }
    }
    func recoverTree(_ root: TreeNode?) {
        guard let root = root else {
            return
        }
        inorderTraverse(root)
        let num = samllerNode!.val
        samllerNode?.val = (biggerNode?.val)!
        biggerNode?.val = num
    }
    
    // MARK: - *********** 【100】相同的树 难度:简单 ***********
    /**
     给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     示例1
     输入：p = [1,2,3], q = [1,2,3]
     输出：true
     
     示例2
     输入：p = [1,2], q = [1,null,2]
     输出：false
     
     示例3
     输入：p = [1,2,1], q = [1,1,2]
     输出：false
     */
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        return (p == nil && q == nil) || (p?.val == q?.val) && isSameTree(p?.right, q?.right) && isSameTree(p?.left, q?.left)
    }
    
    func isSameTree2(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        if p?.val != q?.val {
            return false
        }
        if p?.left == nil && q?.left == nil && p?.right == nil && q?.right == nil {
            return true
        }else{
            return isSameTree2(p?.left,q?.left) && isSameTree2(p?.right, q?.right)
        }
    }
    
    func isSameTree3(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        //递归
        if let p = p,let q = q {
            return p.val == q.val && isSameTree3(p.left, q.left) && isSameTree3(p.right, q.right)
        }else{
            return p == nil && q == nil
        }
    }
    
    // MARK: - *********** 【101】对称二叉树 难度:简单 ***********
    /**
     给你一个二叉树的根节点 root ， 检查它是否轴对称
     示例1
     输入：root = [1,2,2,3,4,4,3]
     输出：true
     
     示例2
     输入：root = [1,2,2,null,3,null,3]
     输出：false
     */
    func isSymmetric(_ root: TreeNode?) -> Bool {
        return checkTree(root, root)
    }
    
    func checkTree(_ left: TreeNode?,_ right: TreeNode?) -> Bool {
        if left == nil || right == nil {
            return left == nil && right == nil
        }
        if left?.val != right?.val {
            return false
        }
        return checkTree(left?.left, right?.right) && checkTree(left?.right, right?.left)
    }
    
    func DFS(_ left: TreeNode?,_ right: TreeNode?) -> Bool {
        //左子树为空且右子树为空
        if left == nil && right == nil { return true }
        //左子树不为空且右子树不为空，左子树val不等于右子树val
        if left != nil && right != nil && left?.val != right?.val { return false }
        //左子树为空且右子树不为空、左子树不为空且右子树不为空
        if (left == nil && right != nil) || (left != nil && right == nil) {
            return false
        }
        if (left != nil && right != nil && left?.val != right?.val) {return false}
        //如果结果不正确，直接返回false
        //比较左子树的左节点和右子树的右节点
        if !DFS(left?.left, right?.right) {return false}
        //比较左子树的右节点和右子树的左节点
        if !DFS(left?.right, right?.left) {return false}
        return true
    }
    
    func DFS2(_ left: TreeNode?,_ right: TreeNode?) -> Bool {
        if left == nil && right == nil {return true}
            
        if left == nil || right == nil {return false}
            
        if left?.val != right?.val {return false}
        
        return DFS2(left?.left, right?.right) && DFS2(left?.right, right?.left)
    }
    
    // MARK: - *********** 【102】二叉树的层序遍历 难度:中等 ***********
    /**
     示例1
     输入：root = [3,9,20,null,null,15,7]
     输出：[[3],[9,20],[15,7]]
     
     示例2
     输入：root = [1]
     输出：[[1]]
     */
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let temp = root else {
            return []
        }
        var result = Array<Array<Int>>()
        recursive(temp, 0, &result)
        return result
    }
    
    func recursive(_ node: TreeNode?,_ level: Int,_ result: inout Array<Array<Int>>){
        guard let temp = node else {
            return
        }
        if result.count - 1 < level {
            let curLevels = Array<Int>()
            result.append(curLevels)
        }
        result[level].append(temp.val)
        recursive(temp.left, level + 1, &result)
        recursive(temp.right, level + 1, &result)
    }
    
    func levelOrder2(_ root: TreeNode?) -> [[Int]] {
        var result = [[Int]]()
        var nodeValues = [Int]()
        var current = [TreeNode]()
        var next = [TreeNode]()
        guard let node = root else {
            return result
        }
        current.append(node)
        while !current.isEmpty {
            let t = current.removeFirst()
            if t.left != nil {
                next.append(t.left!)
            }
            if t.right != nil {
                next.append(t.right!)
            }
            nodeValues.append(t.val)
            if current.isEmpty {
                current = next
                next.removeAll()
                result.append(nodeValues)
                nodeValues.removeAll()
            }
        }
        return result
    }
    
    // MARK: - *********** 【103】二叉树的锯齿形层序遍历 难度:中等 ***********
    /**
     给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
     */
    func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else {
            return []
        }
        var result = [[Int]]()
        var order = true
        var queue = [TreeNode]()
        queue.append(root)
        while !queue.isEmpty {
            var levelNodes = [Int]()
            let count = queue.count
            for _ in 0..<count{
                let node = queue.removeFirst()
                if order {
                    levelNodes.append(node.val)
                }else {
                    levelNodes.insert(node.val, at: 0)
                }
                if let leftNode = node.left {
                    queue.append(leftNode)
                }
                if let rightNode = node.right {
                    queue.append(rightNode)
                }
            }
            result.append(levelNodes)
            order = !order
        }
        return result
    }
}
